#define DEBUG
#include <cstdio>
#include <cmath>
#define MAXN 1000
#define MAXM 1000

using namespace std;

int gcd(int a, int b) {
  for (int r=a%b; r; a=b, b=r, r=a%b);
  return b;
}

int calc(int a, int b) {
  int x=gcd(a, b), p=0;
  for (int i=2; i<=sqrt(x); i++) {
    for (; x%i==0; x/=i) {
      p++;
    }
  }
  return x>1 ? p+1 : p;
}

int main() {
#ifdef DEBUG
  freopen("2.in", "r", stdin);
  freopen("2.out", "w", stdout);
#endif

  int t;
  scanf("%d", &t);
  for (int ti=1; ti<=t; ti++) {
    int n, m, p, ans=0;
    scanf("%d %d %d", &n, &m, &p);
    for (int i=1; i<=n; i++) {
      for (int j=1; j<=m; j++) {
	ans += calc(i, j)<=p;
      }
    }
    printf("%d\n", ans);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
